Horner's method

This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: See Talk:Horner's method#This Article is about Two Different Algorithms. Please help improve this article if you can. (November 2018) (Learn how and when to remove this message)

In mathematics and computer science, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. Although named after William George Horner, this method is much older, as it has been attributed to Joseph-Louis Lagrange by Horner himself, and can be traced back many hundreds of years to Chinese and Persian mathematicians.^[1] After the introduction of computers, this algorithm became fundamental for computing efficiently with polynomials.

The algorithm is based on Horner's rule, in which a polynomial is written in nested form: $${\displaystyle {\begin{aligned}&a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\={}&a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}}$$

This allows the evaluation of a polynomial of degree n with only ${\displaystyle n}$ multiplications and ${\displaystyle n}$ additions. This is optimal, since there are polynomials of degree n that cannot be evaluated with fewer arithmetic operations.^[2]

Alternatively, Horner's method and Horner–Ruffini method also refers to a method for approximating the roots of polynomials, described by Horner in 1819. It is a variant of the Newton–Raphson method made more efficient for hand calculation by application of Horner's rule. It was widely used until computers came into general use around 1970.